package erChaShuFuXi;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class erChaShuLianXi3{
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }

  }

  //关于二叉树的层次遍历
    //无返回的写法
  public void levelOrder3(TreeNode root) {
      if (root == null) {
          return;
      }
      TreeNode cur=root;
      Queue<TreeNode> queue=new LinkedList<>();
      queue.offer(cur);
      while(!queue.isEmpty()){
          int size=queue.size();
          while (size!=0) {
              TreeNode chu = queue.poll();
              System.out.print(chu.val + " ");
              if (chu.left != null) {
                  queue.offer(chu.left);
              }
              if(chu.right!=null) {
                  queue.offer(chu.right);
              }
              size--;
          }
          System.out.println();
      }
      return;
  }

  //力扣写法
  public List<List<Integer>> levelOrder(TreeNode root) {
      List<List<Integer>> list=new LinkedList<>();
      if(root==null){
          return list;
      }
      Queue<TreeNode> queue=new LinkedList<>();
      queue.offer(root);
      while(!queue.isEmpty()){
          int size=queue.size();
          LinkedList<Integer> ret=new LinkedList<>();
          while(size!=0){
              TreeNode cur=queue.poll();
              ret.add(cur.val);
              if(cur.left!=null){
                  queue.offer(cur.left);
              }
              if(cur.right!=null){
                  queue.offer(cur.right);
              }
              size--;
          }
          list.add(ret);
      }
      return list;
  }
  //找公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode leftTree= lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if(leftTree!=null&&rightTree!=null){
            return root;
        }else if(leftTree!=null){
            return leftTree;
        }else{
            return rightTree;
        }
    }
}
